Search Results

Documents authored by Iacono, John

Document
DOI: 10.4230/DagRep.13.5.114
Scalable Data Structures (Dagstuhl Seminar 23211)

Authors: Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23211 "Scalable Data Structures". Data structures enable the organization, storage and retrieval of data across a variety of applications. As they are deployed at unprecedented scales, data structures can profoundly affect the efficiency of almost all computational tasks. The study of data structures thus continues to be an important and active area of research with an interplay between data structure design and analysis, developments in computer hardware, and the needs of modern applications. The extended abstracts included in this report give a snapshot of the current state of research on scalable data structures and establish directions for future developments in the field.
Cite as

Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant. Scalable Data Structures (Dagstuhl Seminar 23211). In Dagstuhl Reports, Volume 13, Issue 5, pp. 114-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.13.5.114,
  author =	{Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin},
  title =	{{Scalable Data Structures (Dagstuhl Seminar 23211)}},
  pages =	{114--135},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.5.114},
  URN =		{urn:nbn:de:0030-drops-193676},
  doi =		{10.4230/DagRep.13.5.114},
  annote =	{Keywords: algorithms, big data, computational models, data structures, GPU computing, parallel computation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.21
External-Memory Dictionaries with Worst-Case Update Cost

Authors: Rathish Das, John Iacono, and Yakov Nekrich

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
The B^ε-tree [Brodal and Fagerberg 2003] is a simple I/O-efficient external-memory-model data structure that supports updates orders of magnitude faster than B-tree with a query performance comparable to the B-tree: for any positive constant ε < 1 insertions and deletions take O(1/B^(1-ε) log_B N) time (rather than O(log_BN) time for the classic B-tree), queries take O(log_B N) time and range queries returning k items take O(log_B N + k/B) time. Although the B^ε-tree has an optimal update/query tradeoff, the runtimes are amortized. Another structure, the write-optimized skip list, introduced by Bender et al. [PODS 2017], has the same performance as the B^ε-tree but with runtimes that are randomized rather than amortized. In this paper, we present a variant of the B^ε-tree with deterministic worst-case running times that are identical to the original’s amortized running times.
Cite as

Rathish Das, John Iacono, and Yakov Nekrich. External-Memory Dictionaries with Worst-Case Update Cost. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2022.21,
  author =	{Das, Rathish and Iacono, John and Nekrich, Yakov},
  title =	{{External-Memory Dictionaries with Worst-Case Update Cost}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.21},
  URN =		{urn:nbn:de:0030-drops-173060},
  doi =		{10.4230/LIPIcs.ISAAC.2022.21},
  annote =	{Keywords: Data Structures, External Memory, Buffer Tree}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.39
Conditional Lower Bounds for Dynamic Geometric Measure Problems

Authors: Justin Dallant and John Iacono

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word-RAM model, conditioned on the hardness of either 3SUM, APSP, or the Online Matrix-Vector Multiplication problem [Henzinger et al., STOC 2015]. In particular we get lower bounds in the incremental and fully-dynamic settings for counting maximal or extremal points in ℝ³, different variants of Klee’s Measure Problem, problems related to finding the largest empty disk in a set of points, and querying the size of the i'th convex layer in a planar set of points. We also answer a question of Chan et al. [SODA 2022] by giving a conditional lower bound for dynamic approximate square set cover. While many conditional lower bounds for dynamic data structures have been proven since the seminal work of Pătraşcu [STOC 2010], few of them relate to computational geometry problems. This is the first paper focusing on this topic. Most problems we consider can be solved in O(nlog n) time in the static case and their dynamic versions have only been approached from the perspective of improving known upper bounds. One exception to this is Klee’s measure problem in ℝ², for which Chan [CGTA 2010] gave an unconditional Ω(√n) lower bound on the worst-case update time. By a similar approach, we show that such a lower bound also holds for an important special case of Klee’s measure problem in ℝ³ known as the Hypervolume Indicator problem, even for amortized runtime in the incremental setting.
Cite as

Justin Dallant and John Iacono. Conditional Lower Bounds for Dynamic Geometric Measure Problems. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dallant_et_al:LIPIcs.ESA.2022.39,
  author =	{Dallant, Justin and Iacono, John},
  title =	{{Conditional Lower Bounds for Dynamic Geometric Measure Problems}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.39},
  URN =		{urn:nbn:de:0030-drops-169777},
  doi =		{10.4230/LIPIcs.ESA.2022.39},
  annote =	{Keywords: Computational geometry, Fine-grained complexity, Dynamic data structures}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.13
How Fast Can We Play Tetris Greedily with Rectangular Pieces?

Authors: Justin Dallant and John Iacono

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Consider a variant of Tetris played on a board of width w and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it is full. Suppose we want to follow a greedy strategy: let each rectangle fall where it will end up the lowest given the current state of the board. To do so, we want a data structure which can always suggest a greedy move. In other words, we want a data structure which maintains a set of O(n) rectangles, supports queries which return where to drop the rectangle, and updates which insert a rectangle dropped at a certain position and return the height of the highest point in the updated set of rectangles. We show via a reduction from the Multiphase problem [Pătraşcu, 2010] that on a board of width w = Θ(n), if the OMv conjecture [Henzinger et al., 2015] is true, then both operations cannot be supported in time O(n^{1/2-ε}) simultaneously. The reduction also implies polynomial bounds from the 3-SUM conjecture and the APSP conjecture. On the other hand, we show that there is a data structure supporting both operations in O(n^{1/2}log^{3/2}n) time on boards of width n^O(1), matching the lower bound up to an n^o(1) factor.
Cite as

Justin Dallant and John Iacono. How Fast Can We Play Tetris Greedily with Rectangular Pieces?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dallant_et_al:LIPIcs.FUN.2022.13,
  author =	{Dallant, Justin and Iacono, John},
  title =	{{How Fast Can We Play Tetris Greedily with Rectangular Pieces?}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.13},
  URN =		{urn:nbn:de:0030-drops-159839},
  doi =		{10.4230/LIPIcs.FUN.2022.13},
  annote =	{Keywords: Tetris, Fine-grained complexity, Dynamic data structures, Axis-aligned rectangles}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.3
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model

Authors: Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ ∈ C, the number of intersection points between the segments of A and those of B that lie in Δ. The problems considered in this paper have been studied by Chan (2020), who gave algorithms that solve them, in the standard real-RAM model, in O((n²/log²n) log^O(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n^{60/31+ε}), for any ε > 0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl (2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm.
Cite as

Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2021.3,
  author =	{Aronov, Boris and de Berg, Mark and Cardinal, Jean and Ezra, Esther and Iacono, John and Sharir, Micha},
  title =	{{Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.3},
  URN =		{urn:nbn:de:0030-drops-154363},
  doi =		{10.4230/LIPIcs.ISAAC.2021.3},
  annote =	{Keywords: Computational geometry, Algebraic decision-tree model, Polynomial partitioning, Primal-dual range searching, Order types, Point location, Hierarchical partitions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.24
An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility

Authors: Jean Cardinal, Justin Dallant, and John Iacono

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Afshani, Barbay and Chan (2017) introduced the notion of instance-optimal algorithm in the order-oblivious setting. An algorithm A is instance-optimal in the order-oblivious setting for a certain class of algorithms 𝒜 if the following hold: - A takes as input a sequence of objects from some domain; - for any instance σ and any algorithm A' ∈ 𝒜, the runtime of A on σ is at most a constant factor removed from the runtime of A' on the worst possible permutation of σ. If we identify permutations of a sequence as representing the same instance, this essentially states that A is optimal on every possible input (and not only in the worst case). We design instance-optimal algorithms for the problem of reporting, given a bichromatic set of points in the plane S, all pairs consisting of points of different color which span an empty axis-aligned rectangle (or reporting all points which appear in such a pair). This problem has applications for training-set reduction in nearest-neighbour classifiers. It is also related to the problem consisting of finding the decision boundaries of a euclidean nearest-neighbour classifier, for which Bremner et al. (2005) gave an optimal output-sensitive algorithm. By showing the existence of an instance-optimal algorithm in the order-oblivious setting for this problem we push the methods of Afshani et al. closer to their limits by adapting and extending them to a setting which exhibits highly non-local features. Previous problems for which instance-optimal algorithms were proven to exist were based solely on local relationships between points in a set.
Cite as

Jean Cardinal, Justin Dallant, and John Iacono. An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.24,
  author =	{Cardinal, Jean and Dallant, Justin and Iacono, John},
  title =	{{An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.24},
  URN =		{urn:nbn:de:0030-drops-146057},
  doi =		{10.4230/LIPIcs.ESA.2021.24},
  annote =	{Keywords: computational geometry, instance-optimality, colored point sets, empty rectangles, visibility}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.25
Worst-Case Efficient Dynamic Geometric Independent Set

Authors: Jean Cardinal, John Iacono, and Grigorios Koumoutsos

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present a data structure that maintains a constant-factor approximate maximum independent set for broad classes of fat objects in d dimensions, where d is assumed to be a constant, in sublinear worst-case update time. This gives the first results for dynamic independent set in a wide variety of geometric settings, such as disks, fat polygons, and their high-dimensional equivalents. For axis-aligned squares and hypercubes, our result improves upon all (recently announced) previous works. We obtain, in particular, a dynamic (4+ε)-approximation for squares, with O(log⁴ n) worst-case update time. Our result is obtained via a two-level approach. First, we develop a dynamic data structure which stores all objects and provides an approximate independent set when queried, with output-sensitive running time. We show that via standard methods such a structure can be used to obtain a dynamic algorithm with amortized update time bounds. Then, to obtain worst-case update time algorithms, we develop a generic deamortization scheme that with each insertion/deletion keeps (i) the update time bounded and (ii) the number of changes in the independent set constant. We show that such a scheme is applicable to fat objects by showing an appropriate generalization of a separator theorem. Interestingly, we show that our deamortization scheme is also necessary in order to obtain worst-case update bounds: If for a class of objects our scheme is not applicable, then no constant-factor approximation with sublinear worst-case update time is possible. We show that such a lower bound applies even for seemingly simple classes of geometric objects including axis-aligned rectangles in the plane.
Cite as

Jean Cardinal, John Iacono, and Grigorios Koumoutsos. Worst-Case Efficient Dynamic Geometric Independent Set. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.25,
  author =	{Cardinal, Jean and Iacono, John and Koumoutsos, Grigorios},
  title =	{{Worst-Case Efficient Dynamic Geometric Independent Set}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.25},
  URN =		{urn:nbn:de:0030-drops-146061},
  doi =		{10.4230/LIPIcs.ESA.2021.25},
  annote =	{Keywords: Maximum independent set, deamortization, approximation}
}
Document
DOI: 10.4230/DagRep.11.1.1
Scalable Data Structures (Dagstuhl Seminar 21071)

Authors: Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran

Published in: Dagstuhl Reports, Volume 11, Issue 1 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21071 "Scalable Data Structure". Even if the field of data structures is quite mature, new trends and limitations in computer hardware together with the ever-increasing amounts of data that need to be processed raise new questions with respect to efficiency and continuously challenge the existing models of computation. Thermal and electrical power constraints have caused technology to reach "the power wall" with stagnating single processor performance, meaning that all nontrivial applications need to address scalability with multiple processors, a memory hierarchy and other communication challenges. Scalable data structures are pivotal to this process since they form the backbone of the algorithms driving these applications. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Cite as

Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran. Scalable Data Structures (Dagstuhl Seminar 21071). In Dagstuhl Reports, Volume 11, Issue 1, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.11.1.1,
  author =	{Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya},
  title =	{{Scalable Data Structures (Dagstuhl Seminar 21071)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{1},
  editor =	{Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.1.1},
  URN =		{urn:nbn:de:0030-drops-143481},
  doi =		{10.4230/DagRep.11.1.1},
  annote =	{Keywords: algorithms, big data, data structures, GPU computing, large data sets, models of computation, parallel algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.58
External Memory Planar Point Location with Fast Updates

Authors: John Iacono, Ben Karsin, and Grigorios Koumoutsos

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We study dynamic planar point location in the External Memory Model or Disk Access Model (DAM). Previous work in this model achieves polylog query and polylog amortized update time. We present a data structure with O(log_B^2 N) query time and O(1/B^(1-epsilon) log_B N) amortized update time, where N is the number of segments, B the block size and epsilon is a small positive constant, under the assumption that all faces have constant size. This is a B^(1-epsilon) factor faster for updates than the fastest previous structure, and brings the cost of insertion and deletion down to subconstant amortized time for reasonable choices of N and B. Our structure solves the problem of vertical ray-shooting queries among a dynamic set of interior-disjoint line segments; this is well-known to solve dynamic planar point location for a connected subdivision of the plane with faces of constant size.
Cite as

John Iacono, Ben Karsin, and Grigorios Koumoutsos. External Memory Planar Point Location with Fast Updates. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{iacono_et_al:LIPIcs.ISAAC.2019.58,
  author =	{Iacono, John and Karsin, Ben and Koumoutsos, Grigorios},
  title =	{{External Memory Planar Point Location with Fast Updates}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{58:1--58:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.58},
  URN =		{urn:nbn:de:0030-drops-115548},
  doi =		{10.4230/LIPIcs.ISAAC.2019.58},
  annote =	{Keywords: point location, data structures, dynamic algorithms, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.60
External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms

Authors: John Iacono, Riko Jacob, and Konstantinos Tsakalidis

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We present priority queues in the external memory model with block size B and main memory size M that support on N elements, operation Update (a combination of operations Insert and DecreaseKey) in O(1/Blog_{M/B} N/B) amortized I/Os and operations ExtractMin and Delete in O(ceil[(M^epsilon)/B log_{M/B} N/B] log_{M/B} N/B) amortized I/Os, for any real epsilon in (0,1), using O(N/Blog_{M/B} N/B) blocks. Previous I/O-efficient priority queues either support these operations in O(1/Blog_2 N/B) amortized I/Os [Kumar and Schwabe, SPDP '96] or support only operations Insert, Delete and ExtractMin in optimal O(1/Blog_{M/B} N/B) amortized I/Os, however without supporting DecreaseKey [Fadel et al., TCS '99]. We also present buffered repository trees that support on a multi-set of N elements, operation Insert in O(1/Blog_M/B N/B) I/Os and operation Extract on K extracted elements in O(M^{epsilon} log_M/B N/B + K/B) amortized I/Os, using O(N/B) blocks. Previous results achieve O(1/Blog_2 N/B) I/Os and O(log_2 N/B + K/B) I/Os, respectively [Buchsbaum et al., SODA '00]. Our results imply improved O(E/Blog_{M/B} E/B) I/Os for single-source shortest paths, depth-first search and breadth-first search algorithms on massive directed dense graphs (V,E) with E = Omega (V^(1+epsilon)), epsilon > 0 and V = Omega (M), which is equal to the I/O-optimal bound for sorting E values in external memory.
Cite as

John Iacono, Riko Jacob, and Konstantinos Tsakalidis. External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{iacono_et_al:LIPIcs.ESA.2019.60,
  author =	{Iacono, John and Jacob, Riko and Tsakalidis, Konstantinos},
  title =	{{External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{60:1--60:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.60},
  URN =		{urn:nbn:de:0030-drops-111817},
  doi =		{10.4230/LIPIcs.ESA.2019.60},
  annote =	{Keywords: priority queues, external memory, graph algorithms, shortest paths, depth-first search, breadth-first search}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.38
Dynamic Trees with Almost-Optimal Access Cost

Authors: Mordecai Golin, John Iacono, Stefan Langerman, J. Ian Munro, and Yakov Nekrich

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
An optimal binary search tree for an access sequence on elements is a static tree that minimizes the total search cost. Constructing perfectly optimal binary search trees is expensive so the most efficient algorithms construct almost optimal search trees. There exists a long literature of constructing almost optimal search trees dynamically, i.e., when the access pattern is not known in advance. All of these trees, e.g., splay trees and treaps, provide a multiplicative approximation to the optimal search cost. In this paper we show how to maintain an almost optimal weighted binary search tree under access operations and insertions of new elements where the approximation is an additive constant. More technically, we maintain a tree in which the depth of the leaf holding an element e_i does not exceed min(log(W/w_i),log n)+O(1) where w_i is the number of times e_i was accessed and W is the total length of the access sequence. Our techniques can also be used to encode a sequence of m symbols with a dynamic alphabetic code in O(m) time so that the encoding length is bounded by m(H+O(1)), where H is the entropy of the sequence. This is the first efficient algorithm for adaptive alphabetic coding that runs in constant time per symbol.
Cite as

Mordecai Golin, John Iacono, Stefan Langerman, J. Ian Munro, and Yakov Nekrich. Dynamic Trees with Almost-Optimal Access Cost. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{golin_et_al:LIPIcs.ESA.2018.38,
  author =	{Golin, Mordecai and Iacono, John and Langerman, Stefan and Munro, J. Ian and Nekrich, Yakov},
  title =	{{Dynamic Trees with Almost-Optimal Access Cost}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.38},
  URN =		{urn:nbn:de:0030-drops-95017},
  doi =		{10.4230/LIPIcs.ESA.2018.38},
  annote =	{Keywords: Data Structures, Binary Search Trees, Adaptive Alphabetic Coding}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.20
Subquadratic Encodings for Point Configurations

Authors: Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, and Aurélien Ooms

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
For many algorithms dealing with sets of points in the plane, the only relevant information carried by the input is the combinatorial configuration of the points: the orientation of each triple of points in the set (clockwise, counterclockwise, or collinear). This information is called the order type of the point set. In the dual, realizable order types and abstract order types are combinatorial analogues of line arrangements and pseudoline arrangements. Too often in the literature we analyze algorithms in the real-RAM model for simplicity, putting aside the fact that computers as we know them cannot handle arbitrary real numbers without some sort of encoding. Encoding an order type by the integer coordinates of a realizing point set is known to yield doubly exponential coordinates in some cases. Other known encodings can achieve quadratic space or fast orientation queries, but not both. In this contribution, we give a compact encoding for abstract order types that allows efficient query of the orientation of any triple: the encoding uses O(n^2) bits and an orientation query takes O(log n) time in the word-RAM model with word size w >= log n. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 {(log log n)}^2 / log n) bits for realizable order types, giving the first subquadratic encoding for those order types with fast orientation queries. We further refine our encoding to attain O(log n/log log n) query time at the expense of a negligibly larger space requirement. In the realizable case, we show that all those encodings can be computed efficiently. Finally, we generalize our results to the encoding of point configurations in higher dimension.
Cite as

Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, and Aurélien Ooms. Subquadratic Encodings for Point Configurations. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.SoCG.2018.20,
  author =	{Cardinal, Jean and Chan, Timothy M. and Iacono, John and Langerman, Stefan and Ooms, Aur\'{e}lien},
  title =	{{Subquadratic Encodings for Point Configurations}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.20},
  URN =		{urn:nbn:de:0030-drops-87337},
  doi =		{10.4230/LIPIcs.SoCG.2018.20},
  annote =	{Keywords: point configuration, order type, chirotope, succinct data structure}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.13
Subquadratic Algorithms for Algebraic Generalizations of 3SUM

Authors: Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave an O(n^{11/6}) upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three n-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Grønlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing (GPT) problem: "Given n points in the plane, do three of them lie on a line?", a key problem in computational geometry. We prove that there exist bounded-degree algebraic decision trees of depth O(n^{12/7+e}) that solve 3POL, and that 3POL can be solved in O(n^2 (log log n)^{3/2} / (log n)^{1/2}) time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in subquadratic time when the input points lie on o((log n)^{1/6}/(log log n)^{1/2}) constant-degree polynomial curves. This constitutes the first step towards closing the major open question of whether GPT can be solved in subquadratic time. To obtain these results, we generalize important tools - such as batch range searching and dominance reporting - to a polynomial setting. We expect these new tools to be useful in other applications.
Cite as

Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic Algorithms for Algebraic Generalizations of 3SUM. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barba_et_al:LIPIcs.SoCG.2017.13,
  author =	{Barba, Luis and Cardinal, Jean and Iacono, John and Langerman, Stefan and Ooms, Aur\'{e}lien and Solomon, Noam},
  title =	{{Subquadratic Algorithms for Algebraic Generalizations of 3SUM}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.13},
  URN =		{urn:nbn:de:0030-drops-72214},
  doi =		{10.4230/LIPIcs.SoCG.2017.13},
  annote =	{Keywords: 3SUM, subquadratic algorithms, general position testing, range searching, dominance reporting, polynomial curves}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.25
Solving k-SUM Using Few Linear Queries

Authors: Jean Cardinal, John Iacono, and Aurélien Ooms

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
The k-SUM problem is given n input real numbers to determine whether any k of them sum to zero. The problem is of tremendous importance in the emerging field of complexity theory within P, and it is in particular open whether it admits an algorithm of complexity O(n^c) with c<d where d is the ceiling of k/2. Inspired by an algorithm due to Meiser (1993), we show that there exist linear decision trees and algebraic computation trees of depth O(n^3 log^2 n) solving k-SUM. Furthermore, we show that there exists a randomized algorithm that runs in ~O(n^{d+8}) time, and performs O(n^3 log^2 n) linear queries on the input. Thus, we show that it is possible to have an algorithm with a runtime almost identical (up to the +8) to the best known algorithm but for the first time also with the number of queries on the input a polynomial that is independent of k. The O(n^3 log^2 n) bound on the number of linear queries is also a tighter bound than any known algorithm solving k-SUM, even allowing unlimited total time outside of the queries. By simultaneously achieving few queries to the input without significantly sacrificing runtime vis-a-vis known algorithms, we deepen the understanding of this canonical problem which is a cornerstone of complexity-within-P. We also consider a range of tradeoffs between the number of terms involved in the queries and the depth of the decision tree. In particular, we prove that there exist o(n)-linear decision trees of depth ~O(n^3) for the k-SUM problem.
Cite as

Jean Cardinal, John Iacono, and Aurélien Ooms. Solving k-SUM Using Few Linear Queries. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2016.25,
  author =	{Cardinal, Jean and Iacono, John and Ooms, Aur\'{e}lien},
  title =	{{Solving k-SUM Using Few Linear Queries}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.25},
  URN =		{urn:nbn:de:0030-drops-63763},
  doi =		{10.4230/LIPIcs.ESA.2016.25},
  annote =	{Keywords: k-SUM problem, linear decision trees, point location, \$varepsilon\$-nets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.15
Incremental Voronoi diagrams

Authors: Sarah R. Allen, Luis Barba, John Iacono, and Stefan Langerman

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram VD(S) (and several variants thereof) of a set S of n sites in the plane as sites are added to the set. To that effect, we define a general update operation for planar graphs that can be used to model the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in R^3. We show that the amortized number of edge insertions and removals needed to add a new site to the Voronoi diagram is O(n^(1/2)). A matching Omega(n^(1/2)) combinatorial lower bound is shown, even in the case where the graph representing the Voronoi diagram is a tree. This contrasts with the O(log(n)) upper bound of Aronov et al. [Aronov et al., in proc. of LATIN, 2006] for farthest-point Voronoi diagrams in the special case where points are inserted in clockwise order along their convex hull. We then present a semi-dynamic data structure that maintains the Voronoi diagram of a set S of n sites in convex position. This data structure supports the insertion of a new site p (and hence the addition of its Voronoi cell) and finds the asymptotically minimal number K of edge insertions and removals needed to obtain the diagram of S U (p) from the diagram of S, in time O(K polylog n) worst case, which is O(n^(1/2) polylog n) amortized by the aforementioned combinatorial result. The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained explicitly at all times and can be retrieved and traversed in the natural way; this contrasts with other known data structures supporting nearest neighbor queries. Our data structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in O(log n) time, or to determine whether two given sites are neighbors in the Delaunay triangulation.
Cite as

Sarah R. Allen, Luis Barba, John Iacono, and Stefan Langerman. Incremental Voronoi diagrams. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{allen_et_al:LIPIcs.SoCG.2016.15,
  author =	{Allen, Sarah R. and Barba, Luis and Iacono, John and Langerman, Stefan},
  title =	{{Incremental Voronoi diagrams}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.15},
  URN =		{urn:nbn:de:0030-drops-59079},
  doi =		{10.4230/LIPIcs.SoCG.2016.15},
  annote =	{Keywords: Voronoi diagrams, dynamic data structures, Delaunay triangulation}
}
Document
DOI: 10.4230/DagSemProc.10091.2
Mergeable Dictionaries

Authors: John Iacono and Özgür Özkan

Published in: Dagstuhl Seminar Proceedings, Volume 10091, Data Structures (2010)

Abstract
A data structure is presented for the Mergeable Dictionary abstract data type, which supports the following operations on a collection of disjoint sets of totally ordered data: Predecessor-Search, Split and Union. While Predecessor-Search and Split work in the normal way, the novel operation is Union. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Union operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation, and permits the merging of arbitrarily interleaved sets. Our data structure supports all operations, including Union, in O(log n) amortized time, thus showing that interleaved Union operations can be supported at no additional cost vis-a-vis disjoint Union operations.
Cite as

John Iacono and Özgür Özkan. Mergeable Dictionaries. In Data Structures. Dagstuhl Seminar Proceedings, Volume 10091, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{iacono_et_al:DagSemProc.10091.2,
  author =	{Iacono, John and \"{O}zkan, \"{O}zg\"{u}r},
  title =	{{Mergeable Dictionaries}},
  booktitle =	{Data Structures},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10091},
  editor =	{Lars Arge and Erik D. Demaine and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10091.2},
  URN =		{urn:nbn:de:0030-drops-26854},
  doi =		{10.4230/DagSemProc.10091.2},
  annote =	{Keywords: Data structures, amortized analysis}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact